package cn.mengfly.algorithm.collection.queue;

import cn.mengfly.algorithm.sort.SortUtil;

import java.util.function.BiPredicate;

/**
 * 基于有序二叉堆实现的最大优先队列
 * <p>
 * 有序二叉堆特点：父节点比两个子节点都要大/小
 * <p>
 * 不使用指针的情况下，可以使用数组来表示二叉堆
 * <p>
 * 1. 数组从下标1(而不是0)开始进行编号
 * <p>
 * 2. 父节点的位置为k， 子节点的位置为 2k, 2k+1
 * <p>
 * 3. 插入元素的时候，在数组末尾添加元素，然后找父节点，如果父节点比当前新增的元素小/大，那么交换位置（上浮）
 * <p>
 * 4. 删除元素的时候，删除位置1的元素，然后将数组末尾的元素放到位置1，和子节点比较，如果比子节点小/大，那么和子节点中较大的交换位置（下潜）
 *
 * @author Mengfly
 * @date 2021/6/2 22:21
 */
public class HeapPriorityHelper<Key extends Comparable<? super Key>> {

    /**
     * 基于堆的完全二叉树
     */
    private final Key[] pq;

    /**
     * 数据存储在eq[1...N]中，pq[0]没有使用
     */
    private int size = 0;

    private final BiPredicate<Key, Key> comparePredicate;

    @SuppressWarnings("unchecked")
    public HeapPriorityHelper(int max, BiPredicate<Key, Key> comparePredicate) {
        this.pq = (Key[]) new Comparable[max + 1];
        this.comparePredicate = comparePredicate;
    }

    public void insert(Key v) {
        pq[++size] = v;
        swim(size);
    }

    public Key priorityValue() {
        return pq[1];
    }

    public Key delPriorityValue() {
        Key max = pq[1];
        SortUtil.swap(pq, 1, size--);
        pq[size + 1] = null;
        sink(1);
        return max;
    }

    /**
     * 上浮元素
     *
     * @param k 元素位置
     */
    private void swim(int k) {
        while (k > 1 && comparePredicate.test(pq[k / 2], pq[k])) {
            SortUtil.swap(pq, k / 2, k);
            k = k / 2;
        }
    }

    /**
     * 下潜元素
     *
     * @param k 元素位置
     */
    private void sink(int k) {
        while (2 * k <= size) {
            // 找到第一个子节点
            int j = 2 * k;

            // 判断第二个子节点是不是比第一个子节点大，如果大的话使用第二个子节点和父节点进行交换
            if (j < size && comparePredicate.test(pq[j], pq[j + 1])) {
                j++;
            }

            // 如果父节点比子节点小，交换位置
            if (comparePredicate.test(pq[k], pq[j])) {
                SortUtil.swap(pq, k, j);
                k = j;
            } else {
                // 如果父节点比子节点大，结束比较
                break;
            }
        }
    }

    public int size() {
        return size;
    }
}
